package com.mamingchao.basic.arraysort.quicksort;

/**
 * 快速排序--》 双轴快排
 * 1 4 6 9 10  2 3 5 8 7
 * 经典的快速排序，是单轴快排；选定一个轴，比轴大的放到右边；比轴小的放在左边
 * 左边和右边同时 遍历；左边遍历到 大于轴的 和 右边遍历到小于轴的，两个值交换
 *
 * 重新理一下思路
 * 选定一个轴，比轴大的放右边，比轴小的放左边
 * 为了让轴不影响 对比操作，选最右边（或者最左边）的元素当轴
 * 在 left  right -1 的范围 对比排序
 * Created by mamingchao on 2021/3/12.
 */
public class QuickSort1 {
    public static void main(String[] args) {

//        int[] arr = {1,4,6,9,10,2,3,5,8,7};
//        int[] arr = {1,2,3,4,5,6,7,9,8,10};
//        int[] arr = {1,4,6,5,3,2};
//        int[] arr = {1,4,6,9,7,2,3,5,8,10};
        int[] arr = {1,3,4};
        sort(arr,0,arr.length -1 );
        printArr(arr);

    }

    /**
     * 最右边的元素做轴
     *
     * @param arr 待排序原数组
     * @param left 原数组需要 快排的子数组第一个元素 索引位置
     * @param right 原数组需要 快排的子数组最后一个元素 索引位置
     */
    public static void sort(int[] arr,int left,int right) {

        if (left >= right) return;

        int pivot = right;
        //
        int i = left;
        //从右向左遍历的索引
        int j = right - 1;

        while (i <= j) {
            while (arr[i] <= arr[pivot] && i<=j) {
                i++;
            }
            while (arr[j] > arr[pivot] && i<=j){
                j--;
            }

            if (i < j) swap(arr,i,j);
        }

        swap(arr,i,pivot);
        sort(arr,left,i-1);
        sort(arr,i+1,right);

    }



    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
